CS-04 : DATA STRUCTURE THROUGH
'C' & PASCAL JUN 1995
| Time : 2 Hours |
Max. Marks : 60 |
NOTE: Question 1 is compulsory. Attempt any three from the rest. Algorithms should be written near to C or Pascal language statements.
| 1. | (a) | Write a program using pointer feature (in C or Pascal) to return the starting location |
| of the substring within the string or -1 if the substring was not contained in the string. | ||
| (b) | Write the following expressions into Prefix/Postfix form. | |
| X*Y*Z( Postfix) A | B ** C + D * E - A * C (Prefix) |
||
| (c) | write a recursive algorithm that interchanges all left and right children of a Binary tree. | |
| (d) | Write a recursive algorithm for Merge Sort and show how Merge Sort sorts the | |
| sequence 2, 3, 7 12, 8 9, 7, 5, 4 | ||
| 2. | (a) | What are the advantages of doubly linked list compared to linked list ? |
| (b) | Write an algorithm to construct doubly linked list and search for a data. | |
| 3. | (a) | Draw a B-tree by inserting the following data : |
| {10, 2, 61, 25, 18, 16, 35 } | ||
| (b) | Write a recursive algorithm for inserting a node into B-tree. | |
| 4. | (a) | How is an arithmetic expression evaluated internally ? What are its advantages ? |
| (b) | Write an algorithm to convert an arithmetic expression in infix notation to postfix | |
| notation. | ||
| 5. | (a) | What is the difference between DFS and BFS (Breadth First Search ) ? |
| (b) | Write an algorithm to traverse a graph through DFS. | |
| 6. | Write an algorithm to construct a Binary search tree and print it in the sorted order. |